package xio.ccf_201703;

import java.util.*;

/**
 * 地铁修建 201703-4 90分
 * 加了路径压缩，试了PQ 试了不在每一次连通操作完后都去执行两次find()，还是超时.....
 */
public class MetroBuilding {
  
    private int [] id;    // 节点分量标识
    private int [] rank;  //加权（即根节点对应的分量的大小）

    public MetroBuilding(int N) {
        //初始化
        // 因为站点是从1开始的，方便起见数组也从下标1开始，因此数组长度需变为N+1
        this.id = new int[N+1];
        this.rank = new int[N+1];
        for (int i = 1; i <= N; i++){
            id[i] = i;
            rank[i] = 1;
        }
    }
      
    private int find(int p){
        while (p != id[p]){
            id[p] = id[id[p]];  //路径压缩
            p = id[p];
        }
        return p;
    }  

    /*
    连通操作
     */
    private void union(int p, int q){
        int i = find(p);
        int j = find(q);

        if (i == j){
            return;
        }
        if (rank[i] > rank[j]){
            id[j] = i;
            rank[i] += rank[j];
        }else {
            id[i] = j;
            rank[j] += rank[i];
        }
    }  

    /*
    p q是否连通
     */
    private boolean connected(int p, int q){
        return find(p)==find(q);
    }

    /**
     *
     * 以上为路径压缩的加权quick-union 算法
     * 下面是测试用例（即开始解题）
     */

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();

        ArrayList<Edge> srcData=new ArrayList<>();
        for(int i=0;i<m;++i){
            srcData.add(new Edge(scan.nextInt(),scan.nextInt(),scan.nextInt()));
        }

        MetroBuilding f=new MetroBuilding(n);
        Collections.sort(srcData); // 先按从小到大排序 这样最后让1-n连通时的那个edge的天数就是这个路径里最大的，即所求解

        for (Edge edge : srcData) {
            f.union(edge.a, edge.b);
            if (f.connected(1, n)) { //每进行一次连通操作完 就检查一次1-n是否连通
                System.out.println(edge.day);
                return;
            }
        }
    }

    static class Edge implements Comparable<Edge>{

        int a;
        int b;
        int day; //所需天数

        Edge(int a,int b,int day){
            this.a=a;
            this.b=b;
            this.day=day;
        }

        @Override
        public int compareTo(Edge e){
            if(this.day<e.day){
                return -1;
            }
            else if(this.day>e.day){
                return 1;
            }
            else{
                return 0;
            }
        }
    }

}  
  
  
